package org.bear.Integer;

import java.util.*;

public class Solution {

//    输入：nums = [0,1,0,1,0,1,100]
//    输出：100
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int i=0;i<32;i++){
            int sum=0;
            for(int j=0;j<nums.length;j++){
                sum += (nums[j]>>i)&1;
            }
            sum %= 3;
            if (sum==1){
                res = (1<<i)|res;
            }
        }
        return res;
    }


//    输入：words = ["abcw","baz","foo","bar","fxyz","abcdef"]
//    输出：16
//    解释：这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。
    public int maxProduct2(String[] words) {
        List<Set<Integer>> list = new ArrayList<>(Collections.nCopies(26, null));
        int index = 0;
        for(String s : words){
            for(int i=0; i<s.length(); i++){
                Set<Integer> integers = list.get(s.charAt(i) - 'a');
                if (integers == null){
                    integers = new HashSet<>();
                    list.set(s.charAt(i) - 'a', integers);
                }
                integers.add(index);
            }
            index++;
        }
        List<Set<Integer>> noBlank = new ArrayList<>();
        for(Set<Integer> integers : list){
            if (integers != null && integers.size() > 1){
                noBlank.add(integers);
            }
        }

        int res = 0;
        for(int i=0;i<words.length;i++){
            for(int j=i+1;j<words.length;j++){
                boolean allow = true;
                for(Set<Integer> integers : noBlank){
                    if (integers.contains(i) && integers.contains(j)){
                        allow = false;
                        break;
                    }
                }
                if (allow){
                    res = Math.max(res, words[i].length() * words[j].length());
                }
            }

        }
        return res;
    }


    public int maxProduct(String[] words) {
        int[] nums = new int[words.length];
        int index = 0;
        for(String s : words){
            for(int i=0;i<s.length();i++){
                nums[index] = nums[index] | (1 << (s.charAt(i) - 'a'));
            }
            index++;
        }
        int res = 0;
        for(int i=0;i<words.length;i++){
            for(int j=i+1;j<words.length;j++){
                if ((nums[i] & nums[j]) == 0){
                    res = Math.max(res, words[i].length() * words[j].length());
                }
            }
        }
        return res;
    }



    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] nums = {"a","ab","abc","d","cd","bcd","abcd"};
        System.out.println(solution.maxProduct(nums));
    }
}
